{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Fuel Cost to Report to the Capital"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumFuelCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #到达首都的最少油耗"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵 <code>n</code>&nbsp;个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;，且恰好有&nbsp;<code>n - 1</code>&nbsp;条路。<code>0</code>&nbsp;是首都。给你一个二维整数数组&nbsp;<code>roads</code>&nbsp;，其中&nbsp;<code>roads[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;，表示城市&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间有一条&nbsp;<strong>双向路</strong>&nbsp;。</p>\n",
    "\n",
    "<p>每个城市里有一个代表，他们都要去首都参加一个会议。</p>\n",
    "\n",
    "<p>每座城市里有一辆车。给你一个整数&nbsp;<code>seats</code>&nbsp;表示每辆车里面座位的数目。</p>\n",
    "\n",
    "<p>城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。</p>\n",
    "\n",
    "<p>请你返回到达首都最少需要多少升汽油。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/09/22/a4c380025e3ff0c379525e96a7d63a3.png\" style=\"width: 303px; height: 332px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>roads = [[0,1],[0,2],[0,3]], seats = 5\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>\n",
    "- 代表 1 直接到达首都，消耗 1 升汽油。\n",
    "- 代表 2 直接到达首都，消耗 1 升汽油。\n",
    "- 代表 3 直接到达首都，消耗 1 升汽油。\n",
    "最少消耗 3 升汽油。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/16/2.png\" style=\"width: 274px; height: 340px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>\n",
    "- 代表 2 到达城市 3 ，消耗 1 升汽油。\n",
    "- 代表 2 和代表 3 一起到达城市 1 ，消耗 1 升汽油。\n",
    "- 代表 2 和代表 3 一起到达首都，消耗 1 升汽油。\n",
    "- 代表 1 直接到达首都，消耗 1 升汽油。\n",
    "- 代表 5 直接到达首都，消耗 1 升汽油。\n",
    "- 代表 6 到达城市 4 ，消耗 1 升汽油。\n",
    "- 代表 4 和代表 6 一起到达首都，消耗 1 升汽油。\n",
    "最少消耗 7 升汽油。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/09/27/efcf7f7be6830b8763639cfd01b690a.png\" style=\"width: 108px; height: 86px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>roads = [], seats = 1\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>没有代表需要从别的城市到达首都。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>roads.length == n - 1</code></li>\n",
    "\t<li><code>roads[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li><code>roads</code>&nbsp;表示一棵合法的树。</li>\n",
    "\t<li><code>1 &lt;= seats &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-fuel-cost-to-report-to-the-capital](https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-fuel-cost-to-report-to-the-capital](https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[0,2],[0,3]]\\n5', '[[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]]\\n2', '[]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n = len(roads) + 1\n",
    "        g = [[] for i in range(n)]\n",
    "        deg = [0] * n\n",
    "        for i, j in roads:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "            deg[i] += 1\n",
    "            deg[j] += 1\n",
    "        deg[0] += 1\n",
    "\n",
    "        \n",
    "        vis = [False] * n\n",
    "        people = [1] * n\n",
    "        queue = deque()\n",
    "        for idx, i in enumerate(deg):\n",
    "            if i == 1:\n",
    "                queue.append(idx)\n",
    "                vis[idx] = True\n",
    "                people[idx] = 1\n",
    "\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for x in g[node]:\n",
    "                if vis[x]:\n",
    "                    continue\n",
    "                deg[x] -= 1\n",
    "                if deg[x] == 1:\n",
    "                    queue.append(x)  \n",
    "                    vis[x] = True\n",
    "                    for p in g[x]:\n",
    "                        if vis[p]:\n",
    "                            people[x] += people[p]\n",
    "                            ans += math.ceil(people[p] / seats)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(roads) + 1\n",
    "        deg = [0] * n\n",
    "        g = [[] for _ in range(n)]\n",
    "        num = [1] * n\n",
    "        vis = set()\n",
    "        for a, b in roads:\n",
    "            deg[a] += 1\n",
    "            deg[b] += 1\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        q = deque([i for i in range(n) if deg[i] == 1 and i])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            vis.add(node)\n",
    "            ans += ceil(num[node] / seats)\n",
    "            for nx in g[node]:\n",
    "                if nx not in vis:\n",
    "                    deg[nx] -= 1\n",
    "                    num[nx] += num[node]\n",
    "                    if deg[nx] == 1 and nx:\n",
    "                        q.append(nx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        m = len(roads)\n",
    "        ind = [0] * (m + 1)\n",
    "        g = defaultdict(list)\n",
    "        for a, b in roads:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            ind[a] += 1\n",
    "            ind[b] += 1\n",
    "        ans = 0\n",
    "        q = deque([i for i in range(1, m + 1) if ind[i] == 1])\n",
    "        count = [1] * (m + 1) \n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            # print(t, count[t])\n",
    "            ans += (count[t] + seats - 1) // seats\n",
    "            for b in g[t]:\n",
    "                count[b] += count[t]\n",
    "                ind[b] -= 1\n",
    "                if ind[b] == 1 and b != 0:\n",
    "                    q.append(b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n = len(roads)\n",
    "        ind = [0] * (n + 1)\n",
    "        g = defaultdict(list)\n",
    "        for a, b in roads:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            ind[a] += 1\n",
    "            ind[b] += 1\n",
    "        ans = 0\n",
    "        q = deque([i for i in range(1, n + 1) if ind[i] == 1])\n",
    "        count = [1] * (n + 1) \n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            # print(t, count[t])\n",
    "            ans += (count[t] + seats - 1) // seats\n",
    "            for b in g[t]:\n",
    "                count[b] += count[t]\n",
    "                ind[b] -= 1\n",
    "                if ind[b] == 1 and b != 0:\n",
    "                    q.append(b)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n = len(roads) + 1\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        score = [1] * n\n",
    "        p = [-1] * n\n",
    "        p[0] = 0\n",
    "        d = {}\n",
    "        for u, v in roads:\n",
    "            if u in d:\n",
    "                d[u].append(v)\n",
    "            else:\n",
    "                d[u] = [v]\n",
    "            if v in d:\n",
    "                d[v].append(u)\n",
    "            else:\n",
    "                d[v] = [u]\n",
    "        a, i = [0], 0\n",
    "        while i < len(a):\n",
    "            u = a[i]\n",
    "            i += 1\n",
    "            for v in d[u]:\n",
    "                if p[v] == -1:\n",
    "                    p[v] = u\n",
    "                    a.append(v)\n",
    "        res = 0\n",
    "        for i in reversed(range(1, n)):\n",
    "            v = a[i]\n",
    "            u = p[v]\n",
    "            score[u] += score[v]\n",
    "            res += (score[v] + seats - 1) // seats\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n = len(roads) + 1 # n - 1 roads\n",
    "        indegree = collections.defaultdict(int)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for x, y in roads:\n",
    "            indegree[x] += 1\n",
    "            indegree[y] += 1\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        queue = collections.deque([i for i in range(1, n) if indegree[i] ==1])\n",
    "        res = 0\n",
    "        people = [1] * n # [1] won't be used\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            res += math.ceil(people[node] / seats)\n",
    "            for nei in graph[node]:\n",
    "                indegree[nei] -= 1\n",
    "                people[nei] += people[node]\n",
    "                if indegree[nei] == 1 and nei != 0:\n",
    "                    queue.append(nei)\n",
    "        return res\n",
    "\"\"\"\n",
    "贪心，每次从叶节点（度为1）开始遍历，把所有人送到下一个城市（花费ceil(people/seats)），把花费的油加到结果里，直到所有人都到达首都\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n=len(roads)+1\n",
    "        deg = [0]*n\n",
    "        adj=[[] for _ in range(n)]\n",
    "        for u,v in roads:\n",
    "            deg[u]+=1\n",
    "            deg[v]+=1\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "        # cars, empty_seat, cost\n",
    "        dp = [[0,0,0] for _ in range(n)]\n",
    "        vis = [0]*n\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if deg[i]==1:\n",
    "                q.append(i)\n",
    "                dp[i] = [0,0,0]\n",
    "        \n",
    "        for u in q:\n",
    "            if u==0: continue\n",
    "            vis[u] = 1\n",
    "            # drop cars\n",
    "            dp[u][0] -= dp[u][1] // seats\n",
    "            dp[u][1] = dp[u][1]%seats\n",
    "            for v in adj[u]:\n",
    "                if not vis[v]:\n",
    "                            \n",
    "                    if dp[u][1] > 0:\n",
    "                        dp[u][1] -= 1\n",
    "                    else:\n",
    "                        dp[u][1] = seats-1\n",
    "                        dp[u][0] += 1\n",
    "                        \n",
    "                    dp[v][0] += dp[u][0]\n",
    "                    dp[v][1] += dp[u][1]\n",
    "                    dp[v][2] += dp[u][0] + dp[u][2]\n",
    "                \n",
    "                deg[v] -= 1\n",
    "                if deg[v]==1:\n",
    "                    q.append(v)\n",
    "        # print(dp[1])\n",
    "        return dp[0][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        d = {}\n",
    "        start = deque([])\n",
    "        for i in roads:\n",
    "            if i[0] not in d:\n",
    "                d[i[0]] = []\n",
    "            if i[1] not in d:\n",
    "                d[i[1]] = []\n",
    "            d[i[0]].append(i[1])\n",
    "            d[i[1]].append(i[0])\n",
    "        count = [0]*len(d)\n",
    "        dele = [0]*len(d)\n",
    "        ans = 0\n",
    "        car = [[0,0] for i in d]\n",
    "        for i in d:\n",
    "            count[i]=len(d[i])\n",
    "            if i != 0 and len(d[i]) == 1:\n",
    "                start.append([i,1,0])\n",
    "                dele[i] = -1\n",
    "        #print(d,count)\n",
    "        while start:\n",
    "            #print(10000+ans)\n",
    "            t = len(start)\n",
    "            for i in range(t):\n",
    "                q = start.popleft()\n",
    "                q[2]+=1\n",
    "                if q[1]*seats<q[2]:\n",
    "                    q[1]+=1\n",
    "                else:\n",
    "                    while (q[1]-1)*seats>=q[2]:\n",
    "                        q[1] -= 1\n",
    "                #print(q,q[1])\n",
    "                ans += q[1]\n",
    "                dele[q[0]] = -1\n",
    "                nextq = -1\n",
    "                for j in d[q[0]]:\n",
    "                    if dele[j] != -1:\n",
    "                        nextq = j\n",
    "                        break\n",
    "                #print(nextq)\n",
    "                if nextq == 0:\n",
    "                    continue\n",
    "                count[nextq] -= 1\n",
    "                #print(count[nextq])\n",
    "                car[nextq][0]+=q[1]\n",
    "                car[nextq][1]+=q[2]\n",
    "                #print(car)\n",
    "                if count[nextq] == 1:\n",
    "                    start.append([nextq]+car[nextq])\n",
    "        return ans\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        if not roads:return 0\n",
    "        G = defaultdict(list)\n",
    "        n = len(roads)+1\n",
    "        O = [0] * n\n",
    "        O[0] = inf\n",
    "        for a,b in roads:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "            O[a] += 1\n",
    "            O[b] += 1\n",
    "        \n",
    "        \n",
    "        Dis = [0] * n\n",
    "        v = [0] * n\n",
    "        st,cnt = [0],0\n",
    "        while st:\n",
    "            temp = st\n",
    "            st = []\n",
    "            while temp:\n",
    "                o = temp.pop()\n",
    "                v[o] = 1\n",
    "                Dis[o] = cnt\n",
    "                for nxt in G[o]:\n",
    "                    if not v[nxt]:\n",
    "                        st.append(nxt)\n",
    "            cnt += 1\n",
    "        Sts = [1] * n\n",
    "        vis = [0] * n\n",
    "        vis[0] = 1\n",
    "        q = []\n",
    "        for idx,i in enumerate(O):\n",
    "            heappush(q,(i,idx))\n",
    "        res = 0\n",
    "        while 0 in vis and q:\n",
    "            _,cur = heappop(q)\n",
    "            if vis[cur]:continue\n",
    "            vis[cur] = 1\n",
    "            for i in G[cur]:\n",
    "                if not i or not vis[i]:nxt = i;break\n",
    "            \n",
    "            while Sts[cur] >= seats:\n",
    "                Sts[cur] -= seats\n",
    "                res += Dis[cur]\n",
    "            if Sts[cur] != 0:\n",
    "                Sts[nxt] += Sts[cur]\n",
    "                res += 1\n",
    "            if nxt:\n",
    "                O[nxt] -= 1\n",
    "                heappush(q,(O[nxt],nxt))\n",
    "            \n",
    "        return res\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        if not roads:\n",
    "            return 0\n",
    "        n = max([max(i) for i in roads])+1\n",
    "        tree = [[] for _ in range(n)]\n",
    "        deg = {}\n",
    "        for p in roads:\n",
    "            tree[p[0]].append(p[1])\n",
    "            tree[p[1]].append(p[0])\n",
    "            if p[0] in deg:\n",
    "                deg[p[0]] += 1\n",
    "            else:\n",
    "                deg[p[0]] = 1\n",
    "            if p[1] in deg:\n",
    "                deg[p[1]] += 1\n",
    "            else:\n",
    "                deg[p[1]] = 1\n",
    "\n",
    "        sta = []\n",
    "        for node in deg:\n",
    "            if deg[node] == 1 and node:\n",
    "                sta.append(node)\n",
    "        \n",
    "        reps = dict(zip(range(n), [1] * n))\n",
    "        ans = 0\n",
    "        while sta:\n",
    "            cur = sta.pop()\n",
    "            deg[cur] -= 1\n",
    "            ans += ceil(reps[cur] / seats)\n",
    "            for nxt in tree[cur]:\n",
    "                if deg[nxt] != 0:\n",
    "                    reps[nxt] += reps[cur]\n",
    "                    deg[nxt] -= 1\n",
    "                    if deg[nxt] == 1 and nxt:\n",
    "                        sta.append(nxt)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        d = defaultdict(int)\n",
    "        cnt = defaultdict(int)\n",
    "        for a, b in roads:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            d[a] += 1\n",
    "            d[b] += 1\n",
    "        q = [k for k, v in d.items() if v == 1 and k != 0]\n",
    "        n = len(g)\n",
    "        for i in range(n):\n",
    "            cnt[i] = 1\n",
    "        q = deque(q)\n",
    "        vis = set()\n",
    "        ans = 0\n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            ans += math.ceil(cnt[t] / seats)\n",
    "            vis.add(t)\n",
    "            for node in g[t]:\n",
    "                if node not in vis:\n",
    "                    cnt[node] += cnt[t]\n",
    "                    d[node] -= 1\n",
    "                    if d[node] == 1 and node != 0:\n",
    "                        q.append(node)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        adjList = [set() for i in range(len(roads) + 1)]\n",
    "        for x in roads:\n",
    "            adjList[x[0]].add(x[1])\n",
    "            adjList[x[1]].add(x[0])\n",
    "        stack, res = [[0, 1]], 0\n",
    "        while stack:\n",
    "            if adjList[stack[-1][0]]:\n",
    "                stack.append([adjList[stack[-1][0]].pop(), 1])\n",
    "                adjList[stack[-1][0]].remove(stack[-2][0])\n",
    "            elif len(stack) > 1:\n",
    "                res += (stack[-1][1] - 1) // seats + 1\n",
    "                stack[-2][1] += stack.pop()[1]\n",
    "            else:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        nbs = defaultdict(set)\n",
    "        for u, v in roads:\n",
    "            nbs[u].add(v)\n",
    "            nbs[v].add(u)\n",
    "        c2p = defaultdict(lambda: 1)\n",
    "        \n",
    "        q = queue.Queue()\n",
    "        for c, bs in nbs.items():\n",
    "            if len(bs) == 1:\n",
    "                q.put(c)\n",
    "        count = 0\n",
    "        # ss = 0\n",
    "        if q.empty():\n",
    "            return 0\n",
    "        while not q.empty():\n",
    "            # ss += 1\n",
    "            # if ss == 100:\n",
    "            #     break\n",
    "            c = q.get()\n",
    "            if c == 0:\n",
    "                continue\n",
    "            p = c2p[c]\n",
    "            # print('c', c)\n",
    "            # print('p', p)\n",
    "            # print(nbs)\n",
    "            count += p // seats + (p % seats > 0)\n",
    "            nex = [i for i in nbs[c]][0]\n",
    "            nbs[nex].remove(c)\n",
    "            c2p[nex] += p\n",
    "            # print(nex, nbs[nex])\n",
    "            \n",
    "            if len(nbs[nex]) == 1:\n",
    "                q.put(nex)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        \n",
    "        n = len(roads)+1\n",
    "        if n==1:\n",
    "            return 0\n",
    "        graph = dict()\n",
    "        for item in roads:\n",
    "            if graph.get(item[0],-1)==-1:\n",
    "                graph[item[0]] = set()\n",
    "            if graph.get(item[1],-1)==-1:\n",
    "                graph[item[1]] = set()\n",
    "            graph[item[0]].add(item[1])\n",
    "            graph[item[1]].add(item[0])\n",
    "        dis = [n+1]*n\n",
    "        dis[0] = 0\n",
    "        mydeq = deque()\n",
    "        mydeq.append(0)\n",
    "        vis = [False]*n\n",
    "        vis[0] = True\n",
    "        d = 0\n",
    "        while mydeq:\n",
    "            nn = len(mydeq)\n",
    "            for ii in range(nn):\n",
    "                node = mydeq[0]\n",
    "                vis[node] = True\n",
    "                mydeq.popleft()\n",
    "                dis[node] = d\n",
    "                for child in graph[node]:\n",
    "                    if vis[child]:\n",
    "                        continue\n",
    "                    mydeq.append(child)\n",
    "            d+=1\n",
    "        res = 0\n",
    "        people = [1]*n\n",
    "        people[0] = 0\n",
    "        idxs = [ii for ii in range(n)]\n",
    "        def cmp(a,b):\n",
    "            return dis[b]-dis[a]\n",
    "        idxs.sort(key = cmp_to_key(cmp))\n",
    "        idx = 0\n",
    "        vis = [False]*n\n",
    "        vis[0] = True\n",
    "        while idx<n:\n",
    "            if idx+1==n:\n",
    "                break\n",
    "            curr = dis[idxs[idx]]\n",
    "            while idx<n and dis[idxs[idx]]==curr:\n",
    "                vis[idxs[idx]] = True\n",
    "                res+=people[idxs[idx]]//seats+(1 if people[idxs[idx]]%seats!=0 else 0)\n",
    "                for c in graph[idxs[idx]]:\n",
    "                    if vis[c]:\n",
    "                        continue\n",
    "                    people[c]+=people[idxs[idx]]\n",
    "                idx+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n = len(roads) + 1\n",
    "        link = {i: [] for i in range(n)}\n",
    "        target = {i: -1 for i in range(n)}\n",
    "        visit = [0] * n\n",
    "        ans = 0\n",
    "        for road in roads:\n",
    "            link[road[0]].append(road[1])\n",
    "            link[road[1]].append(road[0])\n",
    "        nodes = [0]\n",
    "        layers = [[0]]\n",
    "        while nodes:\n",
    "            new_nodes = []\n",
    "            for node in nodes:\n",
    "                visit[node] = 1\n",
    "                nxt = [neigh for neigh in link[node] if not visit[neigh]]\n",
    "                for ne in nxt:\n",
    "                    target[ne] = node\n",
    "                new_nodes.extend(nxt)\n",
    "            if new_nodes:\n",
    "                layers.append(new_nodes)\n",
    "            nodes = new_nodes\n",
    "        visit = [0] * n\n",
    "        for layer in reversed(layers):\n",
    "            for node in layer:\n",
    "                if node == 0:\n",
    "                    return ans\n",
    "                nxt = target[node]\n",
    "                ans += ceil((1 + visit[node]) / seats)\n",
    "                visit[nxt] += 1 + visit[node]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n=len(roads)+1\n",
    "        dist=[-1]*n\n",
    "        s=set()\n",
    "        visit=[0]\n",
    "        s.add(0)\n",
    "        dct=defaultdict(set)\n",
    "        dct2=defaultdict(int)\n",
    "        for a,b in roads:\n",
    "            dct[a].add(b)\n",
    "            dct[b].add(a)\n",
    "        while visit:\n",
    "            l=[]\n",
    "            for x in visit:\n",
    "                for y in dct[x]:\n",
    "                    if y not in s:\n",
    "                        s.add(y)\n",
    "                        dist[y]=x\n",
    "                        l.append(y)\n",
    "                        dct2[x]+=1\n",
    "            visit=l\n",
    "        arr=[1]*n\n",
    "        v=[]\n",
    "        for i in range(n):\n",
    "            if dct2[i]==0:\n",
    "                v.append(i)\n",
    "  \n",
    "        while v:\n",
    "            l=[]\n",
    "            for x in v:\n",
    "                if x==0:\n",
    "                    continue\n",
    "                dct2[dist[x]]-=1\n",
    "                arr[dist[x]]+=arr[x]\n",
    "                if dct2[dist[x]]==0:\n",
    "                    l.append(dist[x])\n",
    "            v=l\n",
    "            \n",
    "        ans=0\n",
    "        for i in range(1,n):\n",
    "            ans+=ceil(arr[i]/seats)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        city = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        edges = collections.defaultdict(list)\n",
    "        for frm, to in roads:\n",
    "            edges[frm].append(to)\n",
    "            edges[to].append(frm)\n",
    "            indeg[frm] += 1\n",
    "            indeg[to] += 1\n",
    "            city[to] = [1, 1]\n",
    "            city[frm] = [1, 1]\n",
    "        \n",
    "        start = [i for i in edges.keys() if indeg[i] == 1 and i != 0]\n",
    "        succs = collections.deque(start)\n",
    "        res = 0\n",
    "        visited = set()\n",
    "        while succs:\n",
    "            frm = succs.popleft()\n",
    "            visited.add(frm)\n",
    "            for to in edges[frm]:\n",
    "                if to in visited:\n",
    "                    continue\n",
    "                    \n",
    "                indeg[to] -= 1\n",
    "                city[to][0] += city[frm][0]\n",
    "                res += city[frm][1]\n",
    "                if indeg[to] == 1 and to != 0:\n",
    "                    succs.append(to)\n",
    "                    city[to][1] = math.ceil(city[to][0] / seats)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        \n",
    "        def dijkstra(edges: List[List[int]], n: int) -> int:\n",
    "            dct = defaultdict(list)\n",
    "            for i, j in edges:\n",
    "                dct[i].append([j, 1])\n",
    "            heap = [[0, 0]]\n",
    "            res = [-1]*n\n",
    "            while heap:\n",
    "                cost, cur = heappop(heap)\n",
    "                if res[cur-1] != -1:\n",
    "                    continue\n",
    "                res[cur-1] = cost\n",
    "                for i, j in dct[cur]:\n",
    "                    if res[i-1] == -1:\n",
    "                        heappush(heap, [cost+j, i])\n",
    "            return res\n",
    "        \n",
    "        dct = defaultdict(set)\n",
    "        for i, j in roads:\n",
    "            dct[i].add(j)\n",
    "            dct[j].add(i)\n",
    "        dct2 = defaultdict(set)\n",
    "        for i in range(1, len(roads)+1):\n",
    "            dct2[len(dct[i])].add(i)\n",
    "        nums = [[1, 1] for __ in range(len(roads)+1)]  # 人数，车数\n",
    "        res = 0\n",
    "        while dct2[1]:\n",
    "            for i in list(dct2[1]):\n",
    "                res += nums[i][1]\n",
    "                x = list(dct[i])[0]\n",
    "                if x != 0:\n",
    "                    dct2[len(dct[i])].remove(i)\n",
    "                    dct2[len(dct[x])].remove(x)\n",
    "                    dct[x].remove(i)\n",
    "                    nums[x][0] += nums[i][0]\n",
    "                    nums[x][1] += nums[i][1]\n",
    "                    if (nums[x][1]-1)*seats >= nums[x][0]:\n",
    "                        nums[x][1] -= 1\n",
    "                    dct2[len(dct[x])].add(x)\n",
    "                else:\n",
    "                    dct[i].remove(0)\n",
    "                    dct[0].remove(i)\n",
    "                    dct2[1].remove(i)\n",
    "        return res\n",
    "                \n",
    "            \n",
    "            \n",
    "\"\"\"\n",
    "        dijkstra(roads, )\n",
    "        \n",
    " 0\n",
    "123\n",
    "\n",
    " 0\n",
    "145\n",
    "36\n",
    "2\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n = len(roads)+1\n",
    "        self.graph = collections.defaultdict(list)\n",
    "        for r1,r2 in roads:\n",
    "            self.graph[r1].append(r2)\n",
    "            self.graph[r2].append(r1)\n",
    "        self.depth = collections.defaultdict(list)\n",
    "        self.bfs(self.graph)\n",
    "        mx = max(self.depth.keys())\n",
    "        seat = collections.defaultdict(int)\n",
    "        for i in range(n):\n",
    "            seat[i] = 1\n",
    "        res = 0\n",
    "        # print(mx)\n",
    "        # print(self.depth)\n",
    "        # print(seat)\n",
    "        for i in reversed(range(1,mx+1)):\n",
    "            nodes = self.depth[i]\n",
    "            for n in nodes:\n",
    "                res += ((seat[n]-1) // seats + 1)\n",
    "                for to in self.graph[n]:\n",
    "                    seat[to] += seat[n]\n",
    "        return res\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "    def bfs(self,graph):\n",
    "        queue = [0]\n",
    "        hist = set([0])\n",
    "        dep = 0\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                q = queue.pop(0)\n",
    "                for to in graph[q]:\n",
    "                    if(to not in hist):\n",
    "                        queue.append(to)\n",
    "                        hist.add(to)\n",
    "                self.depth[dep].append(q)\n",
    "            dep += 1\n",
    "        \n",
    "                    \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        d=dict()\n",
    "        d2=dict()\n",
    "        n=len(roads)+1\n",
    "        for e in roads:\n",
    "            if e[0] not in d:\n",
    "                d[e[0]]=set()\n",
    "            d[e[0]].add(e[1])\n",
    "            if e[1] not in d:\n",
    "                d[e[1]]=set()\n",
    "            d[e[1]].add(e[0])\n",
    "        for i in range(n):\n",
    "            d2[i]=[1,0]\n",
    "        l=[]\n",
    "        for k in d:\n",
    "            if len(d[k])==1 and k!=0:\n",
    "                l.append([k,d[k].pop()])\n",
    "        while(True):\n",
    "            l2=[]\n",
    "            if len(l)==0:return d2[0][1] \n",
    "            for src,dst in l:\n",
    "                fuel=d2[src][1]\n",
    "                pcnt=d2[src][0]\n",
    "                fuel+=ceil(pcnt/seats)\n",
    "                d2[dst][0]+=pcnt\n",
    "                d2[dst][1]+=fuel\n",
    "                if src in d[dst]:\n",
    "                    d[dst].remove(src)\n",
    "                if len(d[dst])==1 and dst!=0:\n",
    "                    l2.append([dst,d[dst].pop()])\n",
    "            l=l2.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        res = 0\n",
    "        path = defaultdict(list)\n",
    "        for s,e in roads:\n",
    "            path[s].append(e)\n",
    "            path[e].append(s)\n",
    "        visited = {0}\n",
    "        step = [[0]]\n",
    "        p = [0]\n",
    "        state_dict = defaultdict(list)\n",
    "        state = defaultdict(int)\n",
    "        while(len(p)>0):\n",
    "            n = []\n",
    "            for node in p:\n",
    "                for city in path[node]:\n",
    "                    if city not in visited:\n",
    "                        n.append(city)\n",
    "                        visited.add(city)\n",
    "                        state_dict[node].append(city)\n",
    "            if n:\n",
    "                step.append(n)\n",
    "            p = n\n",
    "        for i in range(len(step)-1,-1,-1):\n",
    "            for node in step[i]:\n",
    "                state[node] = 1\n",
    "                if node not in state_dict:\n",
    "                    pass\n",
    "                else:\n",
    "                    for s in state_dict[node]:\n",
    "                        state[node] += state[s]\n",
    "                        res += math.ceil(state[s]/seats)\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        gg = defaultdict(list)\n",
    "        for ii, jj in roads:\n",
    "            g[ii].append(jj)\n",
    "            g[jj].append(ii)\n",
    "        N = len(roads) + 1\n",
    "        done = [0] * N\n",
    "        q = deque([(0, 0)])\n",
    "        done[0] = 1\n",
    "        qq = []\n",
    "        while q:\n",
    "            now, h = q.popleft()\n",
    "            gg[h].append(now)\n",
    "            n = 0\n",
    "            for ii in g[now]:\n",
    "                if done[ii] == 0:\n",
    "                    n += 1\n",
    "                    q.append([ii, h + 1])\n",
    "                    done[ii] = 1\n",
    "\n",
    "        m = max(gg)\n",
    "        done = [0] * N\n",
    "        res =  0\n",
    "        ka = defaultdict(list)\n",
    "        for ii in range(m, -1, -1):\n",
    "            for jj in gg[ii]:\n",
    "                if done[jj] == 1:\n",
    "                    continue\n",
    "                done[jj] = 1\n",
    "                # print(ka[jj])\n",
    "                n = 1 + sum([j * k for i, j, k in ka[jj]])\n",
    "                res += sum([(i - ii) * k for i, j, k in ka[jj]])\n",
    "                ka[jj] = [(ii, seats, (n // seats))]\n",
    "                \n",
    "                if n % seats:\n",
    "                    ka[jj].append((ii, n % seats, 1))\n",
    "                # print(jj, ka[jj])\n",
    "                for kk in g[jj]:\n",
    "                    if done[kk] == 0:\n",
    "                        if jj not in ka:\n",
    "                            ka[kk].append((ii, 1, 1))\n",
    "                        else:\n",
    "                            ka[kk].extend(ka[jj])\n",
    "        return res\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        dic=defaultdict(list)\n",
    "        for item in roads:\n",
    "            dic[item[0]].append(item[1])\n",
    "            dic[item[1]].append(item[0])\n",
    "        inedge=defaultdict(list)\n",
    "        outedge=defaultdict()\n",
    "        v=set()\n",
    "        q=deque()\n",
    "        q.append([0,0])\n",
    "        dic1=defaultdict(list)\n",
    "        dic1[0].append(0)\n",
    "        while q:\n",
    "            cur,depth=q.popleft()\n",
    "            for item in dic[cur]:\n",
    "                if item not in v:\n",
    "                    inedge[cur].append(item)\n",
    "                    outedge[item]=cur\n",
    "                    dic1[depth+1].append(item)\n",
    "                    q.append([item,depth+1])\n",
    "            v.add(cur)\n",
    "        mdepth=max(dic.keys())\n",
    "        num=[1]*(len(roads)+1)\n",
    "        res=0\n",
    "        for i in range(mdepth,0,-1):\n",
    "            for item in dic1[i]:\n",
    "                num[outedge[item]]+=num[item]\n",
    "                if num[item]%seats:\n",
    "                    res+=((num[item]//seats)+1)\n",
    "                else:res+=(num[item]//seats)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def ceiling_division(numer, denom):\n",
    "    return -((-numer)//denom)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n = len(roads) + 1\n",
    "        g = defaultdict(set)\n",
    "        for a,b in roads:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        \n",
    "        stack = [0]\n",
    "        visited = set(stack)\n",
    "        parent = {}\n",
    "        children = defaultdict(set)\n",
    "\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            for nex in g[cur]:\n",
    "                if nex in visited:\n",
    "                    continue\n",
    "                visited.add(nex)\n",
    "                parent[nex] = cur\n",
    "                children[cur].add(nex)\n",
    "                stack.append(nex)\n",
    "        \n",
    "        stack = []\n",
    "        for cur in range(n):\n",
    "            if not children[cur]:\n",
    "                stack.append(cur)\n",
    "        \n",
    "        res = 0\n",
    "        vals = [1 for _ in range(n)]\n",
    "        \n",
    "        res = 0\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if cur == 0:\n",
    "                break\n",
    "            val = ceiling_division(vals[cur], seats)\n",
    "            # print(cur, val)\n",
    "            res += val\n",
    "            nex = parent[cur]\n",
    "            children[nex].remove(cur)\n",
    "            vals[nex] += vals[cur]\n",
    "            if not children[nex]:\n",
    "                stack.append(nex)\n",
    "        \n",
    "        \n",
    "        # print(vals)\n",
    "        # print()\n",
    "        return res\n",
    "                \n",
    "                \n",
    "                \n",
    "            \n",
    "        \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        self.ans = 0\n",
    "        g = [[] for _ in range(len(roads)+1)]\n",
    "        for x, y in roads:\n",
    "            #在这个list里因为是双向路径 所以都添加可以到达的地方\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfs(x, father):\n",
    "            #这一趟加一个人\n",
    "            size = 1\n",
    "            for y in g[x]:\n",
    "                if y != father:\n",
    "                    size += dfs(y, x)\n",
    "            if x != 0:\n",
    "                self.ans += (size + seats - 1)//seats\n",
    "            return size\n",
    "        dfs(0, -1)\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 从尾巴算到开头 一直过来 如果size + seat - 1 /seat \n",
    "# 意思就是把后面这些一起往前运一格 需要几辆车？因为每次都是移动一格 我们只需要算移动这一格\n",
    "# 需要花几辆车的油量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        ans = 0\n",
    "        g = [[] for _ in range(len(roads) + 1)]\n",
    "        for x, y in roads:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfs(x: int, fa: int) -> int:\n",
    "            size = 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    size += dfs(y, x)\n",
    "            if x:\n",
    "                nonlocal ans\n",
    "                ans += (size + seats - 1) // seats\n",
    "            return size\n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        ans = 0\n",
    "        # 建图\n",
    "        graph = [[] for _ in range(len(roads) + 1)]\n",
    "        for x, y in roads:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        visited = [True] + [False] * len(roads)\n",
    "\n",
    "        def dfs(node: int) -> int:\n",
    "            size = 1  # 计算子树的大小，包括当前的节点，所以初始化为 1\n",
    "            for y in graph[node]:\n",
    "                if not visited[y]:\n",
    "                    visited[y] = True\n",
    "                    size += dfs(y)\n",
    "            if node:\n",
    "                nonlocal ans\n",
    "                ans += ceil(size / seats)\n",
    "            return size\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n=len(roads)+1\n",
    "        edge=[[] for _ in range(n+1)]\n",
    "        for l,r in roads:\n",
    "            edge[l].append(r)\n",
    "            edge[r].append(l)\n",
    "        def dfs(f,t):\n",
    "            you,ren=0,1\n",
    "            for x in edge[t]:\n",
    "                if x!=f:\n",
    "                    y,r=dfs(t,x)\n",
    "                    you+=y+(r+seats-1)//seats\n",
    "                    ren+=r\n",
    "            return (you,ren)\n",
    "        return dfs(-1,0)[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n = len(roads) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        vis = [0] * n\n",
    "        for road in roads:\n",
    "            g[road[0]].append(road[1])\n",
    "            g[road[1]].append(road[0])\n",
    "        def dfs(x):\n",
    "            vis[x] = 1\n",
    "            if x != 0 and len(g[x]) == 1:\n",
    "                return 1, 0\n",
    "            p, y = 0, 0\n",
    "            for v in g[x]:\n",
    "                if vis[v] == 1:\n",
    "                    continue\n",
    "                person, you = dfs(v)\n",
    "                p += person\n",
    "                y += (person + seats - 1) // seats + you\n",
    "            return p + 1, y      \n",
    "        ans = dfs(0)\n",
    "        return ans[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        if len(roads) == 0:\n",
    "            return 0\n",
    "        fa_L = [-1] * (len(roads) + 1)  # 记录每个节点的父节点\n",
    "        nei = [[] for i in range(len(roads) + 1)]  # 记录每个节点的相邻节点\n",
    "\n",
    "        for x, y in roads:\n",
    "            nei[x].append(y)\n",
    "            nei[y].append(x)\n",
    "        \n",
    "        def dfs1(nei, fa_L, cur, cur_fa):\n",
    "            fa_L[cur] = cur_fa\n",
    "            for son in nei[cur]:\n",
    "                if son != cur_fa:\n",
    "                    dfs1(nei, fa_L, son, cur)\n",
    "            return fa_L\n",
    "\n",
    "        fa_L = dfs1(nei, fa_L, 0, -1)\n",
    "        \n",
    "        def dfs2(nei, fa_L, cur, seats):\n",
    "            if cur != 0 and len(nei[cur]) == 1:\n",
    "                # 叶节点\n",
    "                # 返回 当前人数，当前汽车数，当前耗油量\n",
    "                return 1, 1, 0\n",
    "            else:\n",
    "                cur_people = 1\n",
    "                cur_car = 0\n",
    "                cur_you = 0\n",
    "                for son in nei[cur]:\n",
    "                    if son != fa_L[cur]:\n",
    "                        son_people, son_car, son_you = dfs2(nei, fa_L, son, seats)\n",
    "                        cur_people += son_people\n",
    "                        cur_car += son_car - 1\n",
    "                        cur_you += son_you + son_car\n",
    "                \n",
    "                extra_car = (cur_people + seats - 1) // seats\n",
    "\n",
    "                return cur_people - (extra_car - 1)  * seats, cur_car + extra_car, cur_you\n",
    "        res = dfs2(nei, fa_L, 0, seats)\n",
    "        return res[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        ans = 0\n",
    "        for a, b in roads:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        def dfs(x, fa):\n",
    "            size = 1\n",
    "            for node in g[x]:\n",
    "                if node != fa:\n",
    "                    size += dfs(node, x)\n",
    "            if x:\n",
    "                nonlocal ans\n",
    "                ans += math.ceil(size / seats)\n",
    "            return size\n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        def dfs(node: int):\n",
    "            indegree[node] = 1\n",
    "\n",
    "            for neighbor in g[node]:\n",
    "                if indegree[neighbor] == 0:\n",
    "                    indegree[node] += dfs(neighbor)\n",
    "\n",
    "            return indegree[node]\n",
    "\n",
    "        # 1. O(E) build adjacent list\n",
    "        n = len(roads) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in roads:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        # 2. O(V) DFS find number of children of each node\n",
    "        indegree = [0]*n\n",
    "        dfs(0)\n",
    "\n",
    "        # 3. O(V) BFS\n",
    "        ans = 0\n",
    "        visited = [False]*n\n",
    "        visited[0] = True \n",
    "        queue = deque([0])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for neighbor in g[node]:\n",
    "                if not visited[neighbor]:\n",
    "                    ans += math.ceil(indegree[neighbor]/ seats)\n",
    "                    queue.append(neighbor)\n",
    "                    visited[neighbor] = True \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        g = [[] for i in range(len(roads) + 1)]\n",
    "        for e in roads:\n",
    "            g[e[0]].append(e[1])\n",
    "            g[e[1]].append(e[0])\n",
    "        res = 0\n",
    "        def dfs(cur, fa):\n",
    "            nonlocal res\n",
    "            peopleSum = 1 \n",
    "            for ne in g[cur]:\n",
    "                if ne != fa:\n",
    "                    peopleCnt = dfs(ne, cur)\n",
    "                    peopleSum += peopleCnt\n",
    "                    res += (peopleCnt + seats - 1) // seats\n",
    "            return peopleSum\n",
    "        dfs(0, -1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        def dfs(node: int, parent: int):\n",
    "            indegree[node] = 1\n",
    "\n",
    "            for neighbor in g[node]:\n",
    "                if neighbor != parent: \n",
    "                    indegree[node] += dfs(neighbor, node)\n",
    "\n",
    "            return indegree[node]\n",
    "        \n",
    "        def bfs(node: int, parent: int):\n",
    "            ans = 0\n",
    "            queue = collections.deque([[node, parent]])\n",
    "\n",
    "            while queue:\n",
    "                node, parent = queue.popleft()\n",
    "                for neighbor in g[node]:\n",
    "                    if neighbor != parent:\n",
    "                        ans += math.ceil(indegree[neighbor]/ seats)\n",
    "                        queue.append([neighbor, node])\n",
    "\n",
    "            return ans \n",
    "\n",
    "        # 1. O(E) build adjacent list\n",
    "        n = len(roads) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in roads:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        # 2. O(V) DFS find indegree of each node (including itself +1)\n",
    "        indegree = [0]*n\n",
    "        dfs(0, -1)\n",
    "\n",
    "        # 3. O(V) BFS sum over fuel of each path\n",
    "        ans = bfs(0, -1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n = len(roads) + 1\n",
    "        es = [[] for i in range(n)]\n",
    "        for a,b in roads:\n",
    "            es[a].append(b)\n",
    "            es[b].append(a)\n",
    "        \n",
    "        def get_res(id, father_id, es):\n",
    "            res = 0\n",
    "            cnt = 1\n",
    "            for nid in es[id]:\n",
    "                if nid == father_id:\n",
    "                    continue\n",
    "                sres, scnt = get_res(nid, id, es)\n",
    "                res += sres\n",
    "                cnt += scnt\n",
    "                res += scnt // seats\n",
    "                if scnt % seats != 0:\n",
    "                    res += 1\n",
    "            return res, cnt\n",
    "        \n",
    "        res, cnt_ = get_res(0, -1, es)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        result = 0\n",
    "        maps = [[] for i in range(len(roads)+1)]\n",
    "        for road in roads:\n",
    "            maps[road[0]].append(road[1])\n",
    "            maps[road[1]].append(road[0])\n",
    "\n",
    "        def dfs(current, maps, seats, next_city):\n",
    "            if len(maps[current]) == 0:\n",
    "                return 0, 1\n",
    "            else:\n",
    "                current_consumption = 0\n",
    "                current_size = 1\n",
    "                for city in maps[current]:\n",
    "                    if city == next_city:\n",
    "                        continue\n",
    "                    past_consumption, past_size = dfs(city, maps,seats, current)\n",
    "                    current_consumption += (past_size + seats - 1) // seats + past_consumption\n",
    "                    current_size += past_size\n",
    "                return current_consumption, current_size\n",
    "        result, _ = dfs(0, maps, seats, None)\n",
    "        return result\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        def f(u, v):\n",
    "            size[u] = 1\n",
    "            for nexts in graph[u]:\n",
    "                if nexts != v:\n",
    "                    f(nexts, u)\n",
    "                    size[u] += size[nexts]\n",
    "                    cost[u] += cost[nexts]\n",
    "                    cost[u] += (size[nexts] - 1) // seats + 1\n",
    "        graph = collections.defaultdict(list)\n",
    "        for r in roads:\n",
    "            graph[r[0]].append(r[1])\n",
    "            graph[r[1]].append(r[0])\n",
    "        n = len(roads) + 1\n",
    "        size = [0] * n\n",
    "        cost = [0] * n\n",
    "        f(0, -1)\n",
    "        return cost[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        # 两遍DFS\n",
    "        n = len(roads) + 1\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in roads:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        sizes = [0] * n\n",
    "        def dfs1(x: int, f: int) -> int:\n",
    "            res = 1\n",
    "            for y in graph[x]:\n",
    "                if y == f:\n",
    "                    continue\n",
    "                res += dfs1(y, x)\n",
    "            sizes[x] = res\n",
    "            return res\n",
    "        dfs1(0, -1)\n",
    "        \n",
    "        def dfs2(x: int, f: int) -> int:\n",
    "            res = 0\n",
    "            for y in graph[x]:\n",
    "                if y == f:\n",
    "                    continue\n",
    "                res += dfs2(y, x) + ceil(sizes[y] / seats)\n",
    "            return res\n",
    "        return dfs2(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: Recursive DFS\n",
    "    time: O(m+n), where m is the edge number, n is the vertex number,\n",
    "        O(n) for m=n.\n",
    "    space: O(n) for the call stack, O(n) for <graph>.\n",
    "    \"\"\"\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        # create a undirected graph\n",
    "        graph = collections.defaultdict(list)\n",
    "        for par, chi in roads:\n",
    "            graph[par].append(chi)\n",
    "            graph[chi].append(par)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        def dfs(node, parent):\n",
    "            nonlocal res\n",
    "            passengers = 0\n",
    "            for child in graph[node]:\n",
    "                if child != parent:\n",
    "                    num = dfs(child, node)\n",
    "                    passengers += num\n",
    "                    res += int(ceil(num / seats))\n",
    "            return passengers + 1\n",
    "        dfs(0, -1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "\n",
    "        res = 0\n",
    "        def dfs(node,parent):\n",
    "            nonlocal res\n",
    "            \n",
    "            cars = empties = 0\n",
    "            \n",
    "            for child in tree[node]:\n",
    "                if child != parent:\n",
    "                    c,s = dfs(child, node)\n",
    "                    cars += c\n",
    "                    empties += s\n",
    "            \n",
    "            res += cars\n",
    "            if empties == 0:\n",
    "                cars += 1\n",
    "                empties = seats-1\n",
    "            else:\n",
    "                people = cars*seats-empties+1\n",
    "                cars = people//seats+bool(people%seats)\n",
    "                empties = cars*seats-people\n",
    "\n",
    "            return cars, empties\n",
    "\n",
    "        tree = collections.defaultdict(list)\n",
    "        for a,b in roads:\n",
    "            tree[a].append(b)\n",
    "            tree[b].append(a)\n",
    "\n",
    "        dfs(0, -1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n = len(roads) + 1\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in roads:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "\n",
    "        def dfs(x, fa):\n",
    "\n",
    "            res = [0, 1]\n",
    "            for y in dct[x]:\n",
    "                if y != fa:\n",
    "                    nex = dfs(y, x)\n",
    "                    res[1] += nex[1]\n",
    "                    res[0] += nex[0] + math.ceil(nex[1]/seats)\n",
    "            return res\n",
    "\n",
    "        return dfs(0, -1)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        e = defaultdict(set)\n",
    "        for u,v in roads:\n",
    "            e[u].add(v)\n",
    "            e[v].add(u)\n",
    "        n = len(roads) + 1\n",
    "        dep = [-1 for _ in range(n)]\n",
    "        dep[0] = 0\n",
    "        queue = deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nxt in e[cur]:\n",
    "                if dep[nxt]  == -1:\n",
    "                    dep[nxt] = dep[cur] + 1\n",
    "                    queue.append(nxt)\n",
    "        cnt = [0 for _ in range(n)]\n",
    "        def dfs(cur):\n",
    "            ans = 1\n",
    "            for nxt in e[cur]:\n",
    "                if dep[nxt] > dep[cur]:\n",
    "                    ans += dfs(nxt)\n",
    "            cnt[cur] = ans\n",
    "            return cnt[cur]\n",
    "        dfs(0)\n",
    "        \n",
    "        # dp1[i],dp2[i]表示所有\n",
    "        fa = [-1 for _ in range(n)]\n",
    "        deg = [0 for _ in range(n)]\n",
    "        for u,v in roads:\n",
    "            if dep[u] > dep[v]:\n",
    "                fa[u] = v\n",
    "                deg[v] += 1\n",
    "            else:\n",
    "                fa[v] = u\n",
    "                deg[u] += 1\n",
    "        dp1,dp2 = [0 for _ in range(n)],[0 for _ in range(n)]\n",
    "        queue = deque()\n",
    "        for i in range(n):\n",
    "            if deg[i] == 0:\n",
    "                queue.append(i)\n",
    "                dp2[i] = 1\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            f = fa[cur]\n",
    "            if f == -1:\n",
    "                continue\n",
    "            deg[f] -= 1\n",
    "            if deg[f] == 0:\n",
    "                nv = 0\n",
    "                vv = 0\n",
    "                for nxt in e[f]:\n",
    "                    if dep[nxt] > dep[f]:\n",
    "                        nv += dp1[nxt]\n",
    "                        vv += dp2[nxt]\n",
    "                if cnt[f] <= seats:\n",
    "                    dp1[f] = nv + vv\n",
    "                    dp2[f] = 1\n",
    "                else:\n",
    "                    dp1[f] = nv + vv\n",
    "                    dp2[f] = math.ceil(cnt[f] / seats)\n",
    "                queue.append(f)\n",
    "        return dp1[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        n=len(roads)+1\n",
    "        edges=defaultdict(set)\n",
    "        for v1,v2 in roads:\n",
    "            edges[v1].add(v2)\n",
    "            edges[v2].add(v1)\n",
    "\n",
    "        res=[0]\n",
    "        def dfs(rt, pa):\n",
    "            cnt=1\n",
    "            for chd in edges[rt]:\n",
    "                if chd==pa: continue\n",
    "                cnt += dfs(chd, rt)\n",
    "            res[0] += ceil(cnt/seats)\n",
    "            return cnt\n",
    "        \n",
    "        for chd in edges[0]:\n",
    "            dfs(chd, 0)\n",
    "\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        d = defaultdict(set)\n",
    "        for i, j in roads:\n",
    "            d[i].add(j)\n",
    "            d[j].add(i)\n",
    "        \n",
    "        res = 0\n",
    "        def df(t, f):\n",
    "            nonlocal res\n",
    "            cars = 0\n",
    "            cities = 0\n",
    "            for i in d[t]:\n",
    "                if i != f:\n",
    "                    car, city = df(i, t)\n",
    "                    cars += car\n",
    "                    cities += city\n",
    "                \n",
    "            res += cars\n",
    "            cities += 1\n",
    "            cars = cities // seats + (cities % seats != 0)\n",
    "            return cars, cities\n",
    "        df(0, -1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "        if not roads:\n",
    "            return 0\n",
    "        vis = set()\n",
    "        vis.add(0)\n",
    "        n = len(roads)+1\n",
    "        g = [set() for _ in range(n)]\n",
    "        for u,v in roads:\n",
    "            g[u].add(v)\n",
    "            g[v].add(u)\n",
    "        res = 0\n",
    "\n",
    "        def dfs(node,dist):\n",
    "            nonlocal res\n",
    "            if not g[node]:\n",
    "                res+=dist\n",
    "                return 1,1\n",
    "            else:\n",
    "                m = seats\n",
    "                tot = 0\n",
    "                num = 0\n",
    "                for child in g[node]:\n",
    "                    if child in vis:\n",
    "                        continue\n",
    "                    else:\n",
    "                        vis.add(child)\n",
    "                        g[child].remove(node)\n",
    "                        tmp,cars = dfs(child,dist+1)                       \n",
    "                        m = min(m,(tmp-1)%seats+1)\n",
    "                        tot+=tmp\n",
    "                        num+=cars\n",
    "                if m==seats:\n",
    "                    res+=dist\n",
    "                    return tot+1,num+1\n",
    "                else:\n",
    "                    emp = num-1-tot//(seats)\n",
    "                    res-=emp*dist\n",
    "                    return tot+1,num-emp\n",
    "        dfs(0,0)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
